﻿//#define TRACE_1
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace ProjectEulerSolutions.Problems
{
    /*
     * Using a combination of black square tiles and oblong tiles chosen from: red tiles measuring two units, green tiles measuring three units, and blue tiles measuring four units, it is possible to tile a row measuring five units in length in exactly fifteen different ways.
				
How many ways can a row measuring fifty units in length be tiled?

NOTE: This is related to problem 116.

     * */
    class Problem117 : IProblem
    {
        public string Calculate()
        {
            int l = 50;
            long c = C(l, 2);

            return c.ToString();
        }

        public long C(int l, int m)
        {
            long count = 1;
            for (int n = 1; n <= l / m; n++)
            {
                for (int k = 0; k <= l - m * n && k <= 2 * n; k++)
                {
#if TRACE_1
                    Console.Write("l = {2}, n = {0}, k = {1}", n, k, l);
#endif
                    long combinations = CommonFunctions.CalculateBinomeBig(l - (m - 1) * n - k, n);
                    long factor = CommonFunctions.CalculateBinomeBig(k + n - 1, n - 1);
#if TRACE_1
                    Console.Write(", combinations = ({2} {3}) {0} * ({1}", combinations, factor, l - (m - 1) * n - k, n);
#endif
                    if (k > 2)
                    {
#if TRACE_1
                        Console.ForegroundColor = ConsoleColor.Green;
                        Console.Write(" - {0}", factor - Combinations(n, k, 0));
                        Console.ForegroundColor = ConsoleColor.Yellow;
                        Console.Write(" = {0}", Combinations(n, k, 0));
                        Console.ForegroundColor = ConsoleColor.Gray;
#endif
                        factor = Combinations(n, k, 0);
                    }
                    //                    if (k > 2)
                    //                    {
                    //                        if (k == 2 * n)
                    //                        {
                    //                            Console.ForegroundColor = ConsoleColor.Red;
                    //                            Console.Write(" - {0}", factor - 1);
                    //                            Console.ForegroundColor = ConsoleColor.Gray;
                    //                            factor = 1;
                    //                        }
                    //                        else if (k >= n)
                    //                        {
                    //                            long subtract = n * CommonFunctions.CalculateBinomeBig(k - 2 + n - 2, n - 1);
                    //#if TRACE_1
                    //                            Console.ForegroundColor = ConsoleColor.Green;
                    //                            Console.Write(" - {0}", subtract);
                    //                            Console.ForegroundColor = ConsoleColor.Gray;
                    //#endif
                    //                            factor -= subtract;
                    //                        }
                    //                        else
                    //                        {
                    //                            long subtract = 0;
                    //                            for (int j = 1; j <= k - 2; j++)
                    //                            {
                    //                                subtract += CommonFunctions.CalculateBinomeBig(n, j);
                    //                            }
                    //#if TRACE_1
                    //                            Console.ForegroundColor = ConsoleColor.Yellow;
                    //                            Console.Write(" - {0}", subtract);
                    //                            Console.ForegroundColor = ConsoleColor.Gray;
                    //#endif
                    //                            factor -= subtract;
                    //                        }
                    //                    }
                    count += combinations * factor;
#if TRACE_1
                    Console.WriteLine("), count = {0}", count);
#endif
                }
            }

            return count;
        }

        Dictionary<string, long> memoization = new Dictionary<string, long>();

        long Combinations(int n, int k, int sum)
        {
            long count = 0;
            for (int i = 0; i <= 2; i++)
            {
                if (n == 1)
                {
                    if (sum + i == k)
                        count++;
                }
                else
                {
                    if (memoization.ContainsKey((n - 1) + ":" + k + ":" + (sum + i)))
                    {
                        count += memoization[(n - 1) + ":" + k + ":" + (sum + i)];
                    }
                    else
                    {
                        count += Combinations(n - 1, k, sum + i);
                    }
                }
            }

            if (!memoization.ContainsKey(n + ":" + k + ":" + sum))
                memoization.Add(n + ":" + k + ":" + sum, count);

            return count;
        }
    }
}
